import java.awt.Point;
import java.util.ArrayList;

public class MazeGen 
{
	private MazeGen(){}
	
	public static class Maze
	{
		int[][] arr;
		int width, height;
		
		Point start;
		Point end;
		
		public Maze(int wid, int hei)
		{
			width = wid;
			height = hei;
			arr = new int[width*2+1][height*2+1];
			start = new Point(1,1);
			end = new Point(2*width-1,2*height-1);
			arr[end.x][end.y] = 1;
		}
		
		public Maze(int wid, int hei, Point St, Point En)
		{
			width = wid;
			height = hei;
			arr = new int[width*2+1][height*2+1];
			start = new Point(St.x*2+1,St.y*2+1);
			end = new Point(En.x*2+1,En.y*2+1);
			arr[end.x][end.y] = 2;
		}
		
		public Maze(int wid, int hei, boolean val)
		{
			width = wid;
			height = hei;
			arr = new int[width*2+1][height*2+1];
			start = new Point((int)(Math.random()*width)*2+1,(int)(Math.random()*height)*2+1);
			end = new Point((int)(Math.random()*width)*2+1,(int)(Math.random()*height)*2+1);
			while(start.x == end.x && start.y == end.y)
				end = new Point((int)(Math.random()*width)*2+1,(int)(Math.random()*height)*2+1);
			arr[end.x][end.y] = 2;
		}
	}
	
	public static Maze generateMaze(int width, int height)
	{
		Maze ret = new Maze(width,height);
		return gen(ret);
	}
	
	public static Maze generateMaze(int width, int height, Point start, Point end)
	{
		Maze ret = new Maze(width,height,start,end);
		return gen(ret);
	}
	
	public static Maze generateRandomMaze(int width, int height)
	{
		Maze ret = new Maze(width,height,true);
		return gen(ret);
	}
	
	private static Maze gen(Maze maze)
	{
		Point brk = openWall(maze.end,maze);
		maze.arr[brk.x][brk.y]= 0; 
		ArrayList<Point> active = new ArrayList<Point>();
		int x = (int)(Math.random()*maze.width)*2+1;
		int y = (int)(Math.random()*maze.height)*2+1;
		active.add(new Point(x,y));
		maze.arr[x][y] = 1;
		while(active.size() > 0)
		{
			int loc = (int)(Math.random()*active.size());
			Point curr = active.remove(loc);
			Point end = openWall(curr,maze);
			if(end != null)
			{
				active.add(curr);
				active.add(end);
			}
		}
		maze.arr[maze.start.x][maze.start.y] = 3;
		return maze;
	}
	
	private static Point openWall(Point curr, Maze maze)
	{
		int dir = (int)(Math.random()*4);
		boolean found = false;
		int x2 = 0, y2 = 0;
		for(int i = 0; i < 4 && !found; i++)
		{
			x2 = curr.x + 2*cos((i+dir)&3);
			y2 = curr.y + 2*sin((i+dir)&3);
			if(x2 > 0 && x2 < 2*maze.width)
				if(y2 > 0 && y2 < 2*maze.height)
					if(maze.arr[x2][y2] == 0)
					{
						found = true;
						dir = (i+dir)&3;
					}
		}
		if(found)
		{
			maze.arr[x2][y2] = 1;
			maze.arr[(curr.x + x2)/2][(curr.y + y2)/2] = 1;
			return new Point(x2,y2);
		}
		return null;
	}
	
	private static int sin(int dir)
	{
		switch(dir)
		{
		case 0:
			return 1;
		case 1:
			return 0;
		case 2:
			return -1;
		case 3:
			return 0;
		default:
			return 0;
		}
	}
	
	private static int cos(int dir)
	{
		switch(dir)
		{
		case 0:
			return 0;
		case 1:
			return 1;
		case 2:
			return 0;
		case 3:
			return -1;
		default:
			return 0;
		}
	}
}
